# @Time    : 2020/6/22 14:45
# @Author  : T-
# @Site    : 
# @File    : 234-Palindrome Linked List.py
# @Software: PyCharm

from utils import ListNode

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        """
        # method-1:将值复制到数组中后用双指针法
        # 时间复杂度:O(n)
        # 空间复杂度:O(n)
        vals = []
        curr_node = head
        while curr_node is not None:
            vals.append(curr_node)
            curr_node = curr_node.next
        return vals == vals[::-1]
        """


        # method-2:快慢指针法
        # 将后半部分链表反转
        # 时间复杂度:O(n)
        # 空间复杂度:O(1)
        if head is None:
            return True
        first_half_end = self.end_of_first_half(head)
        second_half_start = self.reverse_list(first_half_end.next)

        res = True
        first_position = head
        second_position = second_half_start
        while res and second_position is not None:
            if first_position.val != second_position.val:
                return False
            first_position = first_position.next
            second_position = second_position.next
        first_half_end.next = self.reverse_list(second_half_start)
        return res


    # 快慢指针
    # 找到指针前半部分的尾部
    def end_of_first_half(self, head):
        fast = head
        slow = head
        while fast.next is not None and fast.next.next is not None:
            fast = fast.next.next
            slow = slow.next
        return slow

    # 反转链表，具体可见206
    def reverse_list(self, head):
        prev, curr = None, head
        while curr:
            curr.next, prev, curr = prev, curr, curr.next
        return prev
















